package com.shangxia.leetcode.greedyAlgorithm;

import lombok.extern.slf4j.Slf4j;

import java.util.Arrays;

/**
 * @ProjectName: leetcode
 * @ClassName: FindMinArrowShots452
 * @Time: 2020/12/6
 * @Author: zhouy
 * @Description: 452. 用最少数量的箭引爆气球
 * @Experience:
 */

@Slf4j
public class FindMinArrowShots452 {
    public static void main(String[] args) {
        System.out.println(findMinArrowShots2(new int[][]{
                new int[]{9, 12},
                new int[]{1, 10},
                new int[]{4, 11},
                new int[]{8, 12},
                new int[]{3, 9},
                new int[]{6, 9},
                new int[]{6, 7},
        }));
    }

    public static int findMinArrowShots(int[][] points) {
        Arrays.sort(points, (o1, o2) -> {
            if (o1[0] == o2[0]) {
                return Integer.compare(o1[1], o2[1]);
            }
            return Integer.compare(o1[0], o2[0]);
        });
        if (points.length == 0) {
            return 0;
        }
        if (points.length == 1) {
            return 1;
        }
        int index = points[0][1];
        int count = 1;
        for (int[] point : points) {
            if (point[0] > index) {
                index = point[1];
                count++;
            }
            else if (point[1] < index) {
                index = point[1];
            }
        }
        return count;
    }
    public static int findMinArrowShots2(int[][] points) {
        Arrays.sort(points, (p1, p2) -> p1[1] < p2[1] ? -1 : 1);
        if (points.length == 0) {
            return 0;
        }
        if (points.length == 1) {
            return 1;
        }
        int index = points[0][1];
        int count = 1;
        for (int[] point : points) {
            if (point[0] > index) {
                index = point[1];
                count++;
            }
//            else if (point[1] < index) {
//                index = point[1];
//            }
        }
        return count;
    }
}
